#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution03 {
public:
    int maxProfit(int k, vector<int>& prices) {
        // int  n = prices.size();
        // if (n <= 1) return 0;
        // vector<vector<int>> f(n, vector<int>(k + 1));
        // vector<vector<int>> g(n, vector<int>(k + 1));
        // int minz = -0x3f3f3f3f;
        // for (int i = 0; i <= k; i++) {
        //     f[0][i] = minz;
        //     g[0][i] = minz;
        // }
        // f[0][0] = -prices[0];
        // g[0][0] = 0;
        // for (int i = 1; i < n; i++) {
        //     for (int j = 0; j <= k; j++) {
        //         f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
        //         g[i][j] = g[i - 1][j];
        //         if (j >= 1)
        //             g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        //     }
        // }
        // int ret = minz;
        // for (int i = 0; i <= k; i++)
        //     ret = max(ret, g[n - 1][k]);
        // return ret;
        int n = prices.size();
        if (prices.size() <= 1)
            return 0;
        vector<vector<int>> f(n, vector<int>(k + 1));
        vector<vector<int>> g(n, vector<int>(k + 1));
        const int minz = -0x3f3f3f3f;
        for (int i = 0; i < k + 1; i++) {
            f[0][i] = minz;
            g[0][i] = minz;
        }
        g[0][0] = 0;
        f[0][0] = prices[0] * (-1);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < k + 1; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        int ret = minz;
        for (int i = 0; i < k + 1; i++)
            ret = max(ret, g[n - 1][i]);
        return ret;
    }
};

class Solution01 {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n <= 1) return 0;
        vector<int> f(n);
        vector<int> g(n);
        f[0] = (-1) * prices[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return max(f[n - 1], g[n - 1]);
    }
};

class Solution02 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (prices.size() <= 1) return 0;
        vector<vector<int>> f(n, vector<int>(3));
        vector<vector<int>> g(n, vector<int>(3));
        const int minz = -0x3f3f3f3f;
        for (int i = 0; i <= 2; i++) {
            f[0][i] = minz;
            g[0][i] = minz;
        }
        g[0][0] = 0;
        f[0][0] = prices[0] * (-1);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < 3; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        int ret = minz;
        for (int i = 0; i < 3; i++)
            ret = max(ret, g[n - 1][i]);
        return ret;
    }
};

int main() {

	return 0;
}